package leetcode.editor.cn.interview.q17_21

import kotlin.math.max

class Q17_21HardTrap {
    fun trap(height: IntArray): Int {
        var left = 0
        var right = height.size - 1
        var ans = 0
        var leftMax = 0
        var rightMax = 0
        while (left < right) {
            leftMax = max(leftMax, height[left])
            rightMax = max(rightMax, height[right])
            if (height[left] < height[right]) {
                ans += leftMax-height[left]
                left++
            } else {
                ans += rightMax-height[right]
                right--
            }
        }
        return ans
    }
}

fun main() {
    val height = intArrayOf(0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1)
    val q1721hardTrap = Q17_21HardTrap()
    println(q1721hardTrap.trap(height))
}